package _linklist

import org.junit.Assert
import org.junit.Test


/**
 *
 * 24. 两两交换链表中的节点
 * https://leetcode.cn/problems/swap-nodes-in-pairs/description/
 * https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 *
 * 输入：head = []
 * 输出：[]
 *
 * 输入：head = [1]
 * 输出：[1]
 */
class leetcode_24 {
    @Test
    fun test1() {
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        l1.next = l2
        l2.next = l3
        val actual = swapPairs(l1)
        val expect = "2,1,3,"
        Assert.assertEquals(getActual(actual), expect)
    }

    @Test
    fun test2() {
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        val l4 = ListNode(4)
        l1.next = l2
        l2.next = l3
        l3.next = l4
        val actual = swapPairs(l1)
        val expect = "2,1,4,3,"
        Assert.assertEquals(getActual(actual), expect)
    }

    private fun getActual(node: ListNode?): String {
        var s: String = ""
        var p = node
        while (p != null) {
            s = s + p.`val` + ","
            p = p.next
        }
        return s
    }

    class ListNode(var `val`: Int) {
        var next: ListNode? = null
    }

    fun swapPairs(head: ListNode?): ListNode? {
        /**
        1       2       |   3       4     |  NULL
        dummy(current)  left    right       next
        current     left    right       next
        current     left    right

        1       2       |   3       NULL  |
        dummy(current)  left    right       next
        current     left    right       next

        结束条件：
        偶数： left null
        奇数 ：right null
         */
        val dummy: ListNode = ListNode(-1)
        dummy.next = head

        var current: ListNode? = dummy
        var left: ListNode? = current?.next
        var right: ListNode? = left?.next
        var next: ListNode? = right?.next

        // 注意结束条件
        while (left != null && right != null) {
            // 交换
            right.next = left
            left.next = next
            current?.next = right

            // 移动
            // 注意移动时，只移动current，left、right和next要以current为准
            current = current?.next?.next
            left = current?.next
            right = current?.next?.next
            next = current?.next?.next?.next
        }
        return dummy.next
    }
}